package 数据结构OJ;

import java.util.*;

/**
 * @author shy_black
 * @date 2019/4/25 20:22
 * @Description:
 * 解题方法：
 * 1.可以使用小顶堆解决
 *
 * 2.可以利用TreeSet的特性（会按照插入数据自动升序排列）解决
 */
public class 最小的k个数 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        int len = input.length;
        if(input == null || len == 0 || k > len || k <= 0)
            return list;
        TreeSet<Integer> set = new TreeSet<>();
        for(int i = 0;i < len ;i++) {
            if(set.size() < k)
                set.add(input[i]);
            else if(input[i] < set.last()) {
                set.remove(set.last());
                set.add(input[i]);
            }
        }
        Iterator<Integer> i = set.iterator();
        while(i.hasNext()) {
            list.add(i.next());
        }
        return list;
    }
}